package a00_LeetCode.Tree;

import a13_Tree.MyBinTree;
import sun.font.CreatedFontTracker;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author quan
 * @Description 中序遍历的非递归方式：栈
 * @Date 2023/3/28 9:27
 */
public class Num94_middleOrder {
    public List<Integer> inorderTraversal(TreeNode root) {
        //思路：从根节点开始，一直向左走，知道走到第一个左节点。也就是左节点为null，然后此时弹出栈顶元素就是
        //左节点和根节点；当弹出左节点的时候，此时让该节点的右节点入栈，重复上述过程
        //创建集合
        List<Integer> result = new ArrayList<>();
        //创建一个栈
        Deque<TreeNode> stack = new LinkedList<>();
        //边界条件
        if(root == null){
            return result;
        }
        //从根节点开始不断遍历
        TreeNode cur = root;
        while (cur!=null || !stack.isEmpty()){
            //先不断的向左走到头~
            while (cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            //此时cur== null，栈顶就存放了第一个要输出的结点
            //当前栈顶就是第一个左树为空的结点
            cur = stack.pop();
            result.add(cur.val);//此时左子树和根都遍历结束
            //更新cur指针指向右子树，继续右子树
            cur = cur.right;
        }
        return result;
    }
}
